
/**
 * @class
 */
export default class TreeNode {
    /**
     * @param {*} value
     * @param {TreeNode|null} [left]
     * @param {TreeNode|null} [right]
     * @param {number} [count]
     */
    constructor(value, left = null, right = null,count=0) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.count = count; //相同节点数量，主要是为了二叉搜索树不重复
    }
}

// 创建根节点
export const root = new TreeNode("A");
// 创建第二层节点
root.left = new TreeNode("B");
root.right = new TreeNode("C");

// 创建第三层节点
root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");
root.right.left = new TreeNode("F");
root.right.right = new TreeNode("G");

// 创建第四层节点
root.left.left.left = new TreeNode("H");
root.left.left.right = new TreeNode("I");
export let preOrderList=['A','B','D','H','I','E','C','F','G']
export let inOrderList=['H','I','D','B','E','A','F','C','G']
export let postOrderList=['H','I','D','E','B','F','G','C','A']
export let levelOrderList=['A','B','C','D','E','F','G','H','I']

//前序遍历
/**
 * 树的前序遍历
 * @param root 要遍历的根节点
 * @returns {[]|*[]} 前序的结果数组
 */
export function preOrder(root){
    let result=[]
    if(root===null) return [];
    result.push(root.value)
    result=[
        ...result,
        ...preOrder(root.left),
        ...preOrder(root.right)
    ]
    return result
}


//中序遍历
/**
 * 树的中序遍历
 * @param node 要遍历的根节点
 * @returns {[]|*[]} 中序的结果数组
 */
export function inOrder(node){
    if (node===null) return [];
    //遍历左子树
    let leftRes= inOrder(node.left)

    //再遍历右子树
    let rightRes=inOrder(node.right)
    let result=[]
    result=[...leftRes,node.value,...rightRes]
    return result
}


//后序遍历
/**
 * 树的后序遍历
 * @param node 要遍历的根节点
 * @returns {[]|*[]} 后序的结果数组
 */
export function postOrder(node){
    if (node===null) return [];
    //遍历左子树
    let leftRes=postOrder(node.left)
    //再遍历右子树
    let rightRes=postOrder(node.right)
    return [...leftRes,...rightRes,node.value]
}

//层序遍历
/**
 * 树的层序遍历
 * @param root 要遍历的根节点
 * @returns {[]|*[]} 层序的结果数组
 */
export function levelOrder(root){
    if(root===null) return [];
    let res=[]
    const queue=[]
    queue.push(root)
    while (queue.length>0){
        const node=queue.shift() //从队列里拿到放入的节点
        res.push(node.value)
        //把左右子节点入队
        if(node.left !==null) queue.push(node.left)
        if(node.right !==null) queue.push(node.right)
    }
    return res
}

/**
 * 前序中序还原树
 * @param preOrderList
 * @param inOrderList
 * @returns {TreeNode|null}
 */
export function buildTreeByPreOrderListAndInOrderList(preOrderList,inOrderList){
    if(preOrderList.length !== inOrderList.length) {
        throw new Error("长度不一致，无法还原")
    }
    if(preOrderList.length===0) return null
    if(preOrderList.length===1) return new TreeNode(preOrderList[0])
    //从前序遍历中找到目前要构建的子树的根节点
    let rootValue=preOrderList[0]
    let rootIndex=inOrderList.indexOf(rootValue)
    if(rootIndex < 0){
        throw  new  Error("无法在中序遍历中找到对应的根节点，无法还原")
    }
    //把中序分割
    let leftInOrderList=inOrderList.slice(0,rootIndex)
    let rightInOrderList = inOrderList.slice(rootIndex+1)
    //把前序分割
    let leftPreOrderList=preOrderList.slice(1,leftInOrderList.length+1)
    let rightPreOrderList=preOrderList.slice(leftInOrderList.length+1)

    //递归调用
    /** @type {TreeNode} */
    let node=new TreeNode(rootValue)
    node.left=buildTreeByPreOrderListAndInOrderList(leftPreOrderList,leftInOrderList)
    node.right=buildTreeByPreOrderListAndInOrderList(rightPreOrderList,rightInOrderList)
    return node
}

/**
 * 后序中序还原树
 * @param postOrderList
 * @param inOrderList
 * @returns {TreeNode|null}
 */
export function buildTreeByPostOrderListAndInOrderList(postOrderList,inOrderList){
    if(postOrderList.length !== inOrderList.length) {
        throw new Error("长度不一致，无法还原")
    }
    if(postOrderList.length===0) return null
    if(postOrderList.length===1) return new TreeNode(postOrderList[0])
    //从后序遍历中找到目前要构建的子树的根节点:最后一个
    let rootValue=postOrderList[postOrderList.length-1]
    let rootIndex=inOrderList.indexOf(rootValue)
    if(rootIndex < 0){
        throw  new  Error("无法在中序遍历中找到对应的根节点，无法还原")
    }
    //把中序分割
    let leftInOrderList=inOrderList.slice(0,rootIndex)
    let rightInOrderList = inOrderList.slice(rootIndex+1)
    //把后序分割
    let leftPostOrderList=postOrderList.slice(0,leftInOrderList.length)
    let rightPostOrderList=postOrderList.slice(leftInOrderList.length,postOrderList.length-1)

    //递归调用
    /** @type {TreeNode} */
    let node=new TreeNode(rootValue)
    node.left=buildTreeByPostOrderListAndInOrderList(leftPostOrderList,leftInOrderList)
    node.right=buildTreeByPostOrderListAndInOrderList(rightPostOrderList,rightInOrderList)
    return node
}

/**
 * 深度优先搜索（DFS）在二叉树中查找目标值。
 *
 * @param {Object} root - 当前遍历的树节点，格式为 { value, left, right }。
 * @param {Function} callback - 比较目标值的回调,返回true则表示找到
 * @param {Object} result - 用于记录递归过程中的状态：
 *   - isExist: 布尔值，表示是否找到目标值。
 *   - targetNode: 指向找到的目标节点（如果存在）。
 *   - visitOrder: 数组，记录访问节点的顺序。
 *   默认值为 { isExist: false, targetNode: null, visitOrder: [] }。
 *
 * @returns {Object} result - 最终的搜索结果对象。
 *   - isExist: 是否找到目标值。
 *   - targetNode: 目标节点的引用。
 *   - visitOrder: 遍历过程中访问节点的顺序。
 */
export function depthFirstSearch(root, callback, result = { isExist: false, targetNode: null, visitOrder: [] }) {
    // 如果当前节点为空，直接返回当前结果
    if (root === null) return result;

    // 记录当前访问的节点值
    result.visitOrder.push(root.value);

    // 如果当前节点值等于目标值，更新结果并返回
    if (callback(root)) {
        result.isExist = true;
        result.targetNode = root;
        return result;
    }

    // 递归左子树查找
    depthFirstSearch(root.left, callback, result);

    // 如果目标已找到，提前终止递归，避免不必要的搜索
    if (result.isExist === true) return result;

    // 递归右子树查找
    depthFirstSearch(root.right, callback, result);

    // 返回最终结果
    return result;
}


/**
 * 广度优先搜索（BFS）在二叉树中查找目标值。
 *
 * @param {Object} root - 当前遍历的树节点，格式为 { value, left, right }。
 * @param {Function} callback - 比较目标值的回调,返回true则表示找到
 * @param {Object} result - 用于记录递归过程中的状态：
 *   - isExist: 布尔值，表示是否找到目标值。
 *   - targetNode: 指向找到的目标节点（如果存在）。
 *   - visitOrder: 数组，记录访问节点的顺序。
 *   默认值为 { isExist: false, targetNode: null, visitOrder: [] }。
 *
 * @returns {Object} result - 最终的搜索结果对象。
 *   - isExist: 是否找到目标值。
 *   - targetNode: 目标节点的引用。
 *   - visitOrder: 遍历过程中访问节点的顺序。
 */
export function breadthFirstSearch(root, callback, result = { isExist: false, targetNode: null, visitOrder: [] }) {
    // 如果当前节点为空，直接返回当前结果
    if (root === null) return result;
    let queue=[]
    queue.push(root)
    while(queue.length>0){
        let currentNode=queue.shift()
        result.visitOrder.push(currentNode.value)
        if(callback(currentNode)){
            result.isExist=true
            result.targetNode=currentNode
            return result
        }
        if(currentNode.left !==null) queue.push(currentNode.left)
        if(currentNode.right !==null) queue.push(currentNode.right)
    }
    return result
}


/**
 * 严格比较两棵树
 * @param tree1 第一棵树根节点
 * @param tree2 第二棵树根节点
 * @param callback 判断是否相等的函数
 * @returns {boolean|*} 结果
 */
export function StrictCompareTree(tree1,tree2,callback){
    if(tree1===tree2) return true //地址都相同，返回true
    if(!(tree1 && tree2)){
        return false
    }
    if(callback(tree1,tree2)){
        return StrictCompareTree(tree1.left,tree2.left,callback) && StrictCompareTree(tree1.right,tree2.right,callback)
    }
    else{
        return false
    }
}

/**
 * 宽松比较两棵树
 * @param tree1 第一棵树根节点
 * @param tree2 第二棵树根节点
 * @param callback 判断是否相等的函数
 * @returns {boolean|*} 结果
 */
export function CompareTree(tree1,tree2,callback){
    if(tree1===tree2) return true //地址都相同，返回true
    if(!(tree1 && tree2)){
        return false
    }
    if(callback(tree1,tree2)){
        return (CompareTree(tree1.left,tree2.left,callback) && CompareTree(tree1.right,tree2.right,callback))||
            (CompareTree(tree1.right,tree2.left,callback) && CompareTree(tree1.left,tree2.right,callback))
    }
    else{
        return false
    }
}

/**
 * 树比较函数的辅助函数，用于将某个节点的差异记录到结果列表中。
 *
 * @param {'add' | 'delete' | 'valueChange'} type - 差异类型，可能的值有 'add'（新增节点）、'delete'（删除节点）、'valueChange'（节点值变化）。
 * @param {TreeNode|null} node1 - 原树中的节点，可能为 null。
 * @param {TreeNode|null} node2 - 新树中的节点，可能为 null。
 * @param {Array<Object>} resultList - 存储差异信息的数组，会被更新。
 * @returns {Array<Object>} 返回更新后的差异列表。
 */
function handleDiff(type,node1,node2,resultList){
    let item={
        type,
        oldNode: node1,
        newNode: node2,
        change:`${node1?.value ? node1.value : 'null'}-->${node2?.value ? node2.value : 'null'}`

    }
    resultList.push(item)
    return resultList
}

/**
 * 比较两棵二叉树的结构与节点值，记录所有差异（新增、删除、值变化）。
 *
 * @param {TreeNode|null} tree1 - 原始树的根节点。
 * @param {TreeNode|null} tree2 - 要比较的目标树的根节点。
 * @param {Array<Object>} [resultList=[]] - 用于存放差异结果的数组，可选参数，默认是空数组。
 * @returns {Array<Object>} 差异结果数组，每项包含差异类型、旧节点、新节点、变化描述等信息。
 */
export function treeDiff(tree1,tree2,resultList=[]){
    if((tree1===tree2)) return resultList //完全相等
    else if(tree1===null && tree2 !==null){//1.新增
        return handleDiff('add',tree1,tree2,resultList)
    }
    else if(tree1 !== null && tree2 == null){ //2.删除
        return handleDiff('delete',tree1,tree2,resultList)
    }
    else { //3.值修改
        if (tree1?.value !== tree2?.value){
            handleDiff('valueChange',tree1,tree2,resultList)
        }
        //继续左右子树的比较
        treeDiff(tree1.left,tree2.left,resultList)
        treeDiff(tree1.right,tree2.right,resultList)
    }
    return resultList
}

